package com.cat.dataStructure03;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-subarrays-with-majority-element-ii/
 * @create 2025/11/9 20:00
 * @since JDK17
 */

class Solution31 {
    public long countMajoritySubarrays(int[] nums, int target) {
        long ans = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1);
        int sum = 0, c = 0, n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] == target) {
                sum++;
                c += cnt.getOrDefault(sum - 1, 0);
            } else {
                sum--;
                c -= cnt.getOrDefault(sum, 0);
            }
            cnt.merge(sum, 1, Integer::sum);
            ans += c;
        }

        return ans;
    }
}